#include <stdio.h>
#include <stdlib.h>

typedef int E;

struct ListNode {
    E element;
    struct ListNode * Next;
    struct ListNode * Last;
};

typedef struct ListNode * Node;

void  initList(Node node){
    node->Next = node->Last = NULL;
}

_Bool insertList(Node head,E element,int index){
    if (index<1) return 0;
    while (--index){
        head = head -> Next;
        if (head == NULL) return 0;
    }
    Node node = malloc(sizeof(struct ListNode));
    if (node == NULL) return 0;
    node->element = element;
    if(head->Next != NULL) {   //首先处理后继结点，现在有两种情况，一种是后继结点不存在的情况，还有一种是后继结点存在的情况
        head->Next->Last = node;   //如果存在则修改对应的两个指针
        node->Next = head->Next;
    } else {
        node->Next = NULL;   //不存在直接将新结点的后继指针置为NULL
    }
    head -> Next = node;
    node->Last = head;
    return 1;
}

_Bool deleteList(Node head, int index){
    if(index < 1) return 0;   //跟单链表一样，还是先找到对应的位置
    while (--index) {
        head = head->Next;
        if(head == NULL) return 0;
    }
    if(head->Next == NULL) return 0;

    Node temp = head->Next;  //先拿到待删除结点
    if(head->Next->Next) {   //这里有两种情况待删除结点存在后继结点或是不存在
        head->Next->Next->Last = head;
        head->Next = head->Next->Next;   //按照上面分析的来
    }else{
        head->Next = NULL;   //相当于删的是最后一个结点，所以直接后继为NULL就完事
    }
    free(temp);   //最后释放已删除结点的内存
    return 1;
}

int main(){
    struct ListNode head;
    initList(&head);
    for (int i = 1; i <= 5; ++i)  //插5个元素吧
        insertList(&head, i * 100, i);

    deleteList(&head,3);

    Node node = &head;   //先来正向遍历一次
    do {
        node = node->Next;
        printf("%d -> ", node->element);
    } while (node->Next != NULL);

    printf("\n");   //再来反向遍历一次
    do {
        printf("%d -> ", node->element);
        node = node->Last;
    } while (node->Last != NULL);
}
